import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-15
 * Time: 23:28
 */
//https://leetcode.cn/problems/4sum/submissions/653431119/
public class Test {
    public static List<List<Integer>> fourSum(int[] arr, int target) {
        List<List<Integer>> lists=new ArrayList();
        Arrays.sort(arr);
        int i,j,p1,p2;
        long n=0,sum=0,m=0;
        int size=arr.length;
        for( i=0 ;i<size-3;i++){
            n=arr[i];
            n=n*4;
            if(n>target){
                break;
            }
            if(i>0&&arr[i]==arr[i-1]) {
                continue;
            }
            for(j=i+1;j<size-2;j++){
                m=0;
                m=m+arr[i]+arr[j]+arr[j]+arr[j];
                if(m>target){
                    break;
                }
                if(j>i+1&&arr[j]==arr[j-1]){
                    continue;
                }
                p1=j+1;
                p2=size-1;
                while(p1<p2){
                    sum=0;
                    sum=sum+arr[i]+arr[j]+arr[p1]+arr[p2];
                    if(sum<target){
                        p1++;
                    }
                    else if(sum>target){
                        p2--;
                    }
                    else{
                        List list=new ArrayList();
                        list.add(arr[i]);  list.add(arr[j]);  list.add(arr[p1]);  list.add(arr[p2]);
                        lists.add(list);
                        p1++;p2--;
                        while(p1<p2&&arr[p1]==arr[p1-1]){
                            p1++;
                        }
                        while(p1<p2&&arr[p2]==arr[p2+1]){
                            p2--;
                        }
                    }
                }
            }
        }
        return lists;
    }

    public static void main(String[] args) {
        int[] arr={0,4,-5,2,-2,4,2,-1,4};
        List list=fourSum(arr,12);
        System.out.println(list.toString());
    }
}
